什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法的优劣

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。

常见的洗牌算法

方法一：

假如你要洗牌，那么最随机的做法无疑是从牌堆里随便抽一张出来，然后放在一边，之后从剩下的牌里重复之前的操作，直到所有牌都被抽出来放到了另一堆中。抽象到代码世界，按相同的做法，就是随机从数组里取出一个元素，保存到另一个数组，然后重复之，直到原数组中所有元素都处理掉。

                
function shuffle(array) {
    var copy = [],
      n = array.length,
      i;
    // 如果还剩有元素则继续。。。
    while (n) {
        // 随机抽取一个元素
        i = Math.floor(Math.random() * array.length);
        // 如果这个元素之前没有被选中过。。
        if (i in array) {
            copy.push(array[i]);
            delete array[i];
            n--;
        }
    }
    return copy;
}
                
            

方法二：

方法一的问题在此，即使一个序号上的元素已经被处理过了，由于随机函数产生的数是随机的，所有这个被处理过的元素序号可能在之后的循环中不断出现，一是效率问题，另一个就是逻辑问题了，存在一种可能是永远运行不完！

所以改进的做法就是处理完一个元素后，我们用Array的splice()方法将其从目标数组中移除同时也更新了目标数组的长度，如此一来下次遍历的时候是从新的长度开始，不会重复处理的情况了。

                
  function shuffle(array) {
    var copy = [],
        n = array.length,
        i;
    // 如果还剩有元素。。
    while (n) {
        // 随机选取一个元素
        i = Math.floor(Math.random() * n--);
        // 移动到新数组中
        copy.push(array.splice(i, 1)[0]);
    }
    return copy;
}
                
            

最终版：

上面的做法已经可以了，但上面的改进依然还有提升空间。注意到我们要做的仅仅是将数组元素重新排序，已经取出来的元素和剩下的元素之和一定是等于数组原来的总元素个数的。所以可以考虑不创建新的数组来保存已经抽取的元素，可以这样，随机从数组中抽出一个元素，然后与最后个元素交换，相当于把这个随机抽取的元素放到了数组最后面去，表示它已经是被随机过了，同时被换走的那个元素跑到前面去了，会在后续的重复操作中被随机掉。一轮操作过后，下一轮我们只在剩下的n-1个元素也就是数组的前n-1个元素中进行相同的操作，直到进行到第一个。

                
  Array.prototype.shuffle = function() {
    var input = this;
    for (var i = input.length - 1; i >= 0; i--) {
      var randomIndex = Math.floor(Math.random() * (i + 1));//获取小于this.length的随机整数
      var itemAtIdex = input[randomIndex];
      input[randomIndex] = input[i];
      input[i] = itemAtIdex;//input[randomIndex]和input[i]交换值
    }
    return input;
  }